#include <iostream>

using namespace std;

/*
 * 最长公共子串算法
 * 动态规划
 * dp[i][j] = max(dp[i-1][j] + val(str1[i], '-'), dp[i][j-1] + val('-', str2[j]), dp[i-1][j-1] + val(str1[i], str2[j]);
 *
 */

//#define DEBUG

#define MAX_LEN 155
#define MIN     -99999

//下标都是从不开始
//为了解决dp[0][0]
int dp[MAX_LEN][MAX_LEN];
char GSeq1[MAX_LEN];
int GSeq1Len;
char GSeq2[MAX_LEN];
int GSeq2Len;


struct GTable {
    static int T[5][5];

    static int getIndex(char ch) {
        switch(ch) {
            case 'A':
                return 0;
            case 'C':
                return 1;
            case 'G':
                return 2;
            case 'T':
                return 3;
            case '-':
                return 4;
        }
        return -1;
    }

    static int getVal(char a, char b) {
        int i = getIndex(a);
        int j = getIndex(b);

        return T[i][j];
    }
};

int GTable::T[5][5] = 
{
    {5, -1, -2, -1, -3},
    {-1, 5, -3, -2, -4},
    {-2, -3, 5, -2, -2},
    {-1, -2, -2, 5, -1},
    {-3, -4, -2, -1, MIN}
};

void InitDp() {
    for (int i = 1; i <= GSeq1Len; ++i) {
        for (int j = 1; j <= GSeq2Len; ++j) {
            dp[i][j] = 0;
        }
    }
    dp[0][0] = 0;
    for (int i = 1; i <= GSeq2Len; ++i) {
        dp[0][i] = GTable::getVal('-', GSeq2[i-1]) + dp[0][i-1];
    }
    for (int i = 1; i <= GSeq1Len; ++i) {
        dp[i][0] = GTable::getVal(GSeq1[i-1], '-') + dp[i-1][0];
    }
}




#ifdef DEBUG
void PrintDp() {
    cout << "=========>:" << endl;
    for (int i = 0; i <= GSeq1Len; ++i) {
        for (int j = 0; j <= GSeq2Len; ++j) {
            cout << dp[i][j] << " ";
        }
        cout << endl;
    }
    cout << "<=========" << endl;

}
#endif

int max(int a, int b, int c) {
    int t = a > b ? a : b;
    return t > c ? t : c;
}

void Process() {
    InitDp();
#ifdef DEBUG
    cout << GSeq1Len << " :" << GSeq1 << endl;
    cout << GSeq2Len << " :" << GSeq2 << endl;

    PrintDp();
#endif

    for (int i = 1; i <= GSeq1Len; ++i) {
        for (int j = 1; j <= GSeq2Len; ++j) {
            int c1 = GTable::getVal('-', GSeq2[j-1]) + dp[i][j-1];
            int c2 = GTable::getVal(GSeq1[i-1], '-') + dp[i-1][j];
            int c3 = GTable::getVal(GSeq1[i-1], GSeq2[j-1]) + dp[i-1][j-1];
#ifdef DEBUG
            cout << "i: " << i << " j: " << j;
            cout << "c1: " << c1 << " c2:" << c2 << " c3:" << c3 << endl;
#endif
            dp[i][j] = max(c1, c2, c3);
        }
    }
#ifdef DEBUG
    PrintDp();
#endif

    cout << dp[GSeq1Len][GSeq2Len] << endl;



}

int main() {
    int t;
    cin >> t;

    while(t--) {
        cin >> GSeq1Len;
        cin >> GSeq1;
        cin >> GSeq2Len;
        cin >> GSeq2;

        Process();
    }

    return 0;
}
